// H指数

package Leetcode;

import java.util.Arrays;

class Solution_274_1 {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int num = citations.length;
        while (num >= 0) {
            int count = 0;
            for (int i = citations.length - 1; i >= 0; i--) {
                if (citations[i] >= num)
                    count++;
            }
            if (count >= num)
                return num;
            num--;
        }
        return -1;
    }
}

class Solution_274_2 {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0; // h从后往前逐渐递增
        int i = citations.length - 1;
        // 比较 citations[i] > h 如果成立，则会存在 h+1 个大于 h 的书籍
        while (i >= 0 && citations[i] > h) {
            h++;
            i--;
        }
        return h;
    }
}

class Solution_274_3 {
    public int hIndex(int[] citations) {
        int[] count = new int[citations.length + 1];
        for (int i = 0; i < citations.length; i++) {
            if (citations[i] >= citations.length)
                count[citations.length]++;
            else
                count[citations[i]]++;
        }
        int sum = 0;
        for (int i = citations.length; i >= 0; i--) {
            sum += count[i];
            if (sum >= i)
                return i;
        }
        return -1;
    }
}